<h2>Problem 269</h2>
<div style="color:#666;font-size:80%;">19 December 2009</div><br />
<div class="problem_content">
<p>A root or zero of a polynomial P(<var>x</var>) is a solution to the equation P(<var>x</var>) = 0. <br/>
Define P<img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" /> as the polynomial whose coefficients are the digits of <var>n</var>.<br/>
For example, P<img src="" style="display:none;" alt="_(" /><sub>5703</sub><img src="" style="display:none;" alt=")" />(<var>x</var>) = 5<var>x</var><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> + 7<var>x</var><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> + 3.</p>

<p>We can see that:<ul>
<li>P<img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" />(0) is the last digit of <var>n</var>,</li>
<li>P<img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" />(1) is the sum of the digits of <var>n</var>,</li>
<li>P<img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" />(10) is <var>n</var> itself.</li></ul></p>

<p>Define Z(<var>k</var>) as the number of positive integers, <var>n</var>, not exceeding <var>k</var> for which the polynomial P<img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" /> has at least one integer root.</p>

<p>It can be verified that Z(100 000) is 14696.</p>

<p>What is Z(10<img src="" style="display:none;" alt="^(" /><sup>16</sup><img src="" style="display:none;" alt=")" />)?</p>

</div><br />
